The present invention relates generally to routing of data units through a communication network, and more specifically to a system for optimizing network-wide performance metrics when selecting from alternative routes within a deadlock-free set of minimum cost routes.
Routing is the process of determining the network links over which data, such as a packet or other specific type of data unit, is forwarded on its way through a network. Routing is performed by various kinds of data forwarding devices, sometimes referred to as routers and/or switches. A forwarding device that performs routing is typically connected to multiple communication links, and operates to select at least one of those communication links as an output link for each received data unit to be forwarded.
The series of network links between forwarding devices over which data units for a given destination are forwarded from an initial forwarding device to a final forwarding device is referred to as a “route” through a network. Traditional routing systems have generated routing information describing routes through a network that contain no loops. However, even where loop-free routes have been determined, network traffic flows can interact with each other to cause a problem known as “deadlock.”. For example, deadlock can occur within a group of switches, each of which has buffers full of data, and cannot drop any packet from those buffers. Each of the switches in the group may be unable to forward its received data because the next forwarding device to which the data must be forwarded also has no available buffers in which to store the data.
In order to avoid deadlock, existing routing systems have been developed which provide deadlock-free sets of routes by either constraining the topology of the network itself, and/or by constraining the routes which may be taken through the network. For example, the topology of a network may be constrained such that the devices in the network are arranged as a grid. Given a grid topology, if all routes through the network are required to first traverse links horizontally as far as necessary, then vertically to the destination node, the network will be deadlock-free. Similarly, if a network topology is constrained to be a tree, which by definition includes no loops, that network will also be deadlock-free.
In a centralized approach to route generation for a network, a central forwarding device first obtains the complete topology of the network, for example by having each other forwarding device in the network report the neighbor nodes to which it is connected. The central forwarding device then calculates a deadlock-free set of minimum cost routes for the whole network, and stores routing information describing that set of routes within a routing table. Once computed, the routing information can be distributed as forwarding tables to all other forwarding devices in the network, thus informing each forwarding device of the neighbor device to which each received data unit is to be forwarded to, based on the destination of the received data unit.
One existing approach to determining a deadlock-free set of routes through a network is known as “up/down routing.” In up/down routing, one of the forwarding devices in the network is chosen arbitrarily as the root node of a spanning tree for the network. All links within the network are then designated as “up” or “down” links with respect to the root node. The determination of an “up” or “down” state for a given link is based on the position of the link within the spanning tree. A link is “up” if it points from a lower to a higher level node in the tree. Otherwise, the link is considered a “down” link. For nodes at the same level, node IDs are used to break the tie. Routing of packets is performed such that any “up” links (towards the root) in the route are traversed before any “down” links are traversed (away from the root node) in order to reach the destination. Accordingly, once a “down” link has been traversed, no “up” links may be used within that route. This approach is one example of the various existing systems for producing sets of routes that are deadlock-free.
When the set of routes for a network is described by routing information stored in a centrally located routing table, that table may include information describing a number of alternative routes. Some existing systems have randomly selected from alternative routes stored in a central routing table prior to delivering routing information to individual devices. With such centralized selection, the individual forwarding devices in the network are sent forwarding tables that include forwarding information describing only the selected routes. Accordingly, individual forwarding devices such as switches within the network have no opportunity to perform load balancing across alternative routes in order to improve capacity.
In other existing systems, load balancing is addressed by distributing forwarding information that describes alternative routes. After receiving a forwarding table that includes such alternative route information, a forwarding device such as a switch may then independently distribute traffic across the alternative routes to provide load balancing. However, such distributed load balancing, performed independently by individual forwarding devices, is often constrained in its effectiveness by the limited information employed by each forwarding device when selecting between alternative routes. For example, a forwarding device in such a system may perform load balancing across alternative links in response to transmit queue depths for each of its various output ports. Such operation may not provide optimal load balancing on a network wide basis. Moreover, the above described existing systems typically do not perform any optimization with regard to fault tolerance when selecting from alternative routes.
These shortcomings are particularly important in many contemporary high-speed networks, in which performance goals such as optimizing traffic capacity and providing fault tolerance on a network wide basis are very significant. Accordingly, it would be desirable to have a system for selecting between alternative routes, prior to providing routing information from a forwarding table to forwarding devices in a network, that optimizes the selection between alternative routes based on significant network wide performance characteristics, such as traffic capacity and fault tolerance.